\chapter{机器学习笔记}
\section{分类}
\subsection{Logistical 回归}
使用logistical function拟合数据，
\[ p(x)=\frac{e^{\beta_0+\beta_1X}}{1+e^{\beta_0+\beta_1X}} \]

并有，
\[ \ln\frac{p(x)}{1-p(x)} =\beta_0+\beta_1X\]
\subsection{线性判别分析（LDA）}
线性判别分析相对logistic回归有以下优点：
\begin{itemize}
	\item 类别区分度高时，Logistical 回归的参数估计不太稳定，而LDA不存在该问题。
	\item n比较小时，且每个类别的预测变量X近似正态分布时，LDA更稳定。
	\item 响应类别多于2时，LDA的应用更普遍。
\end{itemize}

LDA主要基于贝叶斯定理展开，贝叶斯定理表明，
\begin{equation}\label{chp4-1}
 Pr(Y=k|X=x)=\frac{\pi_kf_k(x)}{\sum_{l=1}^{K}\pi_lf_l(x)}
\end{equation}

其中，$ \pi_k $是一个随机选择的观测来自$ k $的先验概率；$ f_k(x)\equiv Pr(X=x|Y=k) $表示属于第$ k $类观测的$ X $的密度分布函数。一般$ \pi_k $的计算简单，在样本中直接估计即可，但对于$ f_k(x) $稍显复杂。
\subsubsection{$p=1$时的LDA}
要估计$ f_k(x) $可以假设$ f_k(x) $是正态分布，然后估计其均值和方差，
\[ f_k(x)=\frac{1}{\sqrt{2\pi}\sigma_k}exp\left(-\frac{1}{2\sigma^2_k}(x-\mu_k)^2\right) \]

进一步假设各分类的方差相同，即$ \sigma_1=\cdots=\sigma_k=\sigma $，那么将上式代入式\eqref{chp4-1}，可以得到，
\[ p_k(x)=\frac{\pi_k\frac{1}{\sqrt{2\pi}\sigma}exp\left[-\frac{1}{2\sigma^2}(x-\mu_k)\right]}{\sum_{l=1}^{K}\pi_l\frac{1}{\sqrt{2\pi}\sigma}exp\left[-\frac{1}{2\sigma^2}(x-\mu_l)\right]} \]

对于任一观测$ x $，可以计算$K$个$ p_k(x) $，其中最大的就是$ x $所属的分类。上式看起来很复杂，实际上当我们对其取对数，并略去常数项，我们需要计算的仅仅是下式，
\[ \delta_k(x)=x\cdot \frac{\mu_k}{\sigma^2}-\frac{\mu_k^2}{2\sigma^2}+\ln \pi_k \]

当然，要计算它，还需要均值和方差的估计，
\begin{align*}
\hat \mu_k &=\frac{1}{n_k}\sum_{i:y_i=k} x_i\\
\hat \sigma^2 &=\frac{1}{n-K}\sum_{k=1}^{K}\sum_{i:y_i=k} (x_i-\hat{\mu_k}^2)
\end{align*}

其中，$ n $为观测总量，$ n_k $为属于第$ k $类的观测量。
\subsubsection{$p>1$时的LDA}
此时需要假设$ p $维随机变量$ X $服从多元高斯分布，记为$ X\sim N(\mu,\Sigma) $,其密度函数为，
\[ f(x)=\frac{1}{(2\pi)|\Sigma|^{1/2}}exp\left(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)\right) \]

类似地，可以得到仅需计算的式子为，
\[ \delta_k(x)=x^T\Sigma^{-1}\mu_k-\frac{1}{2}\mu_k^T\Sigma^{-1}\mu_k+\ln \pi_k \]

均值和方差的估计类似于$ p=1 $。注意到$ \delta_k $只与$ x $存在线性关系，这正是线性判别的由来。
\subsubsection{二次判别分析：QDA}
如果我们假设每一种分类都有自己的方差，即方差不再恒定时，那么我们需要计算下式来决定分类，
\begin{align*}
 \delta_k(x) & =(x-\mu_k)^T\Sigma^{-1}(x-\mu_k)+\ln \pi_k \\
 & = -\frac{1}{2} x^T\Sigma^{-1}x+x^T\Sigma^{-1}\mu_k-\frac{1}{2}\mu_k^T\Sigma_k^{-1}\mu_k+\ln \pi_k 
\end{align*}
此时，可以看到$ \delta_k $是$ x $的二次函数，这正是QDA名字的由来。
\subsubsection{统计错误的表达}
使用LDA对10000个银行违约的训练数据进行了预测，其混淆矩阵如下，

\begin{table}[h]
\begin{tabular}{c| c|c|c|c}\hline
	& &\multicolumn{3}{|c}{真实违约情况}\\ \cline{3-5}
	& & 没有 & 有& 共计\\ \hline
	\multirow{3}*{估计的违约情况}
		& 没有& 9644 & 252 & 9896 \\
	& 有 & 23 & 81 & 104 \\\cline{2-5}
	& 共计 &9667 & 333 & 10000\\ \hline
	\end{tabular}	
\end{table}
这个表，我们要从总计开始读。真实违约的人有333个，但实际上我们只找出了 81个（找出了104个，但有23个是找错了的），即有252个人漏掉了，这个比率是很高的（75.7\%=252/333）。正确判别违约比例成为\textbf{灵敏度}或者\textbf{真阳性率、势}，也即$1-\text{第二类错误}$;顾名思义，\textbf{假阳性率}就是第一类错误。

这个例子中，势是很低的，即违约的人能甄别出来的很少，这对银行来说是很不利的。对于两类的情况，我们是通过设定$ Pr(default=1|X=x)>0.5 $来将其划为违约者，此时我们希望降低阈值来更多地得到违约者，譬如将阈值设为0.2。这么做，会提高总的错误率，如果提高并不大，这个代价就是值得的。

\subsection{分类方法的比较}
Logisitacl 回归和LDA方法紧密相连，在分类数为2，$ p=1 $时，可以更清楚地看到其关联。在LDA框架下，也可以计算一个$ \ln\frac{p(x)}{1-p(x)} =c_0+c_1x$,而$ c_0,c_1 $是$ \mu_1,\mu_2,\sigma $的函数。可见Logistic和LDA都是$ x $的一个线性函数，不过前者用极大似然估计得到$ \beta_0,\beta_1 $,后者用正态分布的均值和方差得到$ c_0,c_1 $。

而KNN方法是完全非参估计，在高度非线性时该方法可能会优于Logistic和LDA。

而QDA是对KNN和LDA(logistical)的一个折中。



\section{重抽样方法}
\subsection{交叉验证}
\subsubsection{验证集方法}
随机地将数据集分为训练集和验证集，然后计算预测均方误。该法有两大缺陷：
\begin{itemize}
	\item 测试错误率的波动很大；
	\item 只有一部分观测被用于拟合，可能验证集的错误率被高估。
\end{itemize}
\subsubsection{留一交叉验证法}
\begin{enumerate}
	\item 把观测分为两部分，一部分包含一个，剩下的作为训练，这样可以得到只有一个值得均方误$ MSE_1=(y_1-\hat y_1)^2 $
	\item 上述过程重复$ n $次，可以得到均方误的一个估计，
	\[ CV_{(n)}=\frac{1}{n}\sum_{i=1}^{n}MSE_i \]
\end{enumerate}
\subsubsection{$ k $折交叉验证法}
\begin{enumerate}
	\item 把观测随机分为$ k $等份，每一个等份轮流做为验证集，可以得到$ k $个测试误差估计，$ MSE_1,\cdots,MSE_k $;
	\item $ k $折交叉验证的均方误为，
	\[ CV_{(k)}=\frac{1}{k} \sum_{i=1}^k MSE_i \]
\end{enumerate}

可知，当$ k=n $时，该法就是留一交叉验证法。

\section{线性模型选择与正则化}
\subsection{最优子集选择}
\subsubsection{最优子集选择}
选哪些变量最合适？RSS最小的（也即$ R^2 $最大的）最合适。

\begin{enumerate}
	\item 对于$ k=1,2,\cdots,p $，可以拟合$ \big(\begin{smallmatrix}p \\ k\end{smallmatrix}\big) $个包含$ k $个变量的模型，选择其中rss最小的，记为$ M_k $。
	\item 根据预测误差、$ C_p $、AIC、BSC等从$ M_0,M_1,\cdots,M_p $个模型中选出一个最好的。
\end{enumerate}
\subsubsection{逐步选择}
当$ p $很大时，上述方法效率很低，需要其他算法。
向前逐步选择：

\subsection{压缩估计方法}
\subsubsection{岭回归}
最小二乘法是最小化RSS得到系数估计，而岭回归是最小化下式，
\[ RSS+\lambda\sum_{j=1}^{p} \beta_j^2 \]

岭回归的优势在于综合权衡了误差和偏差。一般而言，若自变量与因变量呈线性关系，OLS有较低偏差但有较大方差，即数据的微小改变会导致系数的巨大变化。特别是在$ n $与$ k $差不多大的时候，此时需要岭回归来帮忙。

\subsubsection{lasso}
岭回归也有缺点，即其不会将系数压缩至0，最终总是要包含$ p $个变量。lasso则可以将系数压缩至0，它的原理是最小化下式，
\[ RSS+\lambda\sum_{j=1}^{p} |\beta_j| \]

\subsubsection{岭回归与lasso的比较}
真实模型接近哪个，哪个方法就最好。但是我们并不知道真实模型是什么，实践中还是使用交叉验证来确定哪个是合适的。

\subsection{降维方法}


\section{基于树的方法}
\subsection{树的基本原理}
建立一棵树的大体思路如下，
\begin{enumerate}
	\item 把自变量$ X_1,X_2,\cdots,X_p $的可能取值构成的集合分割成$J$个互不重叠的区域$ R_1,\cdots,R_J $。直接的划分并不可行，一般采用自上而下的贪婪方法：递归二叉分裂:
	\begin{enumerate}
		\item 对于某一自变量$ X_j $以及其分割点s,可以定义一对半平面，
		\[ R_1(j,s)=\{X|X_j<s\} \quad and \quad R_2(j,s)=\{X|X_j\ge s\}\]
		\item 寻找$ j $和$ s $,使得下式最小，
		\[ \sum_{i:x_i\in R_1(j,s)}(y_i-\hat y_{R_1})^2+ \sum_{i:x_i\in R_2(j,s)}(y_i-\hat y_{R_2})^2\]
		\item 重复上述步骤，对每个半平面继续寻找分割的最优自变量和最优分割点。直至某一阈值，譬如每个区域内观测个数小于5。
	\end{enumerate}
	\item 把落入同一区域的观测做出同样的预测，该预测等于该区域训练集上因变量的简单平均。
\end{enumerate}

一般来说树的方法会过拟合，造成预测效果不佳，因此，我们需要一棵分裂点更少，规模更小的树，这就要剪枝\footnote{怎么减？可能会考虑只有RSS超过某个阈值才进行分裂，这种考虑是短视的，因为起初不值得分裂的点在之后却产生了很好的分裂。}。一般来说，也可以通过最小化RSS然后再加上一个惩罚项，如对每一个非负调整参数$ \alpha $，其对应子树的结点数记为$ |T| $，那么最小化下式就可以得到想要的树，
\[ \sum_{m=1}^{|T|}\sum_{i:x_i\in R_m} (y_i-\hat y_{R_m})^2+\alpha |T| \]

其中$ \hat y_{R_m} $是对应于$ R_m $的预测值(也是$R_m$中训练集的平均值)。

包含剪枝的回归树算法总结如下：
\begin{enumerate}
	\item 首先生产一颗大树
	\item 然后对于每一个$ \alpha $就对应一棵树
	\item 使用$ k $折交叉验证确定$ \alpha $，也就确定了子树。
\end{enumerate}
\subsection{分类树}
如果响应变量是定性的，那么就是分类树。此时RSS无法作为分裂准则，一个自然的替代就是\textbf{分类错误率}，
\[ E=1-\max_k(\hat p_{mk}) \]

其中$ \hat p_{mk} $表示$ m $区域中第$ k $类所占的比例。但该指标不敏感，实践中，经常选用其他两个指标。一是\textbf{基尼系数}，
\[ G=\sum_{k=1}^{K}\hat p_{mk}(1-\hat p_{mk}) \]

衡量的是$ K $个类别的总方差，不难发现如果$ \hat p_{mk} $接近0或者1，基尼系数都很小，因此其也称为纯度指标。

二是\textbf{互熵}，定义如下，
\[ D=-\sum_{k=1}^K \hat p_{mk}\ln \hat p_{mk} \]

其与基尼系数十分类似。

\paragraph{树与线性模型的比较}
传统线性模型假设如下模型，
\[ f(X)=\beta_0+\sum_{j=1}^{P} X_j\beta_j \]

回归树假设了如下模型，
\[ f(X)=\sum_{m=1}^{M} c_m\cdot 1_{X\in R_m} \]

在线性假设下，前者更好，如果呈现高度复杂性，则后者更好。

\subsection{装袋法、随机森林和提升法}
回归树的预测性能一般无法达到其他回归和分类的水平，需要其他辅助方法组合大量的树提高回归树的预测效果。
\subsubsection{装袋法}
该法就类似于自助法，但略有不同。该法比较直观，首先自助抽样以得到$ B $个训练集，从而得到$ B $个回归树$ \hat f^1(x),\hat f^2(x),\cdots,\hat f^B(x) $，每个回归树都能给出一个预测结果(记住，此处是回归树而不是分类树)，把这些预测结果平均就是装袋法的预测结果，
\[ \hat f_{bag}(x)=\frac{1}{B}\sum_{b=1}^{B}\hat f^{b}(x) \]

\textbf{如果是分类树，则采取多数投票原则确定所属的类。}

但这样平均之后，解释性大幅下降，此时可以用$ RSS $来对各变量的\textbf{重要性进行度量}，即序贯记录下每个自变量引发的分裂而减小的$RSS$的总量，对该总量在全部树上取平均，结果值越大，说明该自变量越重要。
\subsubsection{随机森林}
基本原理：如果数据集有一个很强预测能力的自变量再加上几个中等强度预测能力的自变量，则用装袋法会使得最强变量在顶部，多数树看起来很相似。而我们知道，相关变量求平均其方差下降远不如不相关变量求平均下降快，因此，可以通过每次自助抽样时，只抽取自变量总数的一部分，譬如$ m=\sqrt{p} $，来重新进行装袋法的运算过程。这种每次自主抽样都修改了自变量个数的方式即为随机森林。

\subsubsection{提升法}
该法相对于前两者的区别在于，生成自助样本集后，每次使用上一次模型的残差作为本次的因变量来生成回归树，具体地，
\begin{enumerate}
	\item 对训练集中的所有个体，令$ \hat f(x)=0 ,r_i=y_i$;
	\item 对$ b=1,2,\cdots,B $,重复如下过程，
\begin{enumerate}
	\item 对训练数据$ (X,r) $建立一棵$ d $个分裂点的树$ \hat f^b $.
	\item 将压缩后的新树加入模型以更新$\hat f$:
	\[ \hat f(x)\leftarrow \hat f(x)+\lambda \hat f^b(x) \]
	\item 更新残差：
	\[ r_i\leftarrow r_i-\lambda\hat f^b(x_i) \]
\end{enumerate}
\item 输出经过提升的模型：
\[ \hat f(x)=\sum_{b=1}^{B}\lambda \hat f^b(x) \]
\end{enumerate}

\section{SVM}
\textbf{超平面}：一个p维的空间，其p-1维的平面仿射子空间就是超平面。
\subsection{二维空间的情况}
在二维空间中，直线就是其超平面，即其可由$ f(x)=\beta_0+\beta^Tx=0 $所定义。其具备如下性质：
\begin{itemize}
	\item 对于超平面L（即直线）上的任意两个点$ x_1,x_2 $，可知$ \beta^T(x_1-x_2)=0 $。从向量的观点看，$ x_1-x_2 $就表示了该条直线，而$ \beta^T $与其正交，可见$ \beta^T $是其法向量，那么$ \beta^*=\beta/\parallel \beta\parallel $就是其单位法向量。
	\item 对于L上的任何点$ x_0 $，满足$ \beta^Tx_0=-\beta_0 $。
	\item 由线代知识，任何点$ x $到L的符号距离为该点减去$ L $上任一点乘以法向量，即
	\begin{align*}
	\beta^{*T}(x-x_0)& =\frac{\beta^T(x-x_0)}{\parallel\beta\parallel} =\frac{\beta^Tx-\beta^T x_0}{\parallel\beta\parallel}\\
	& = \frac{\beta^Tx+\beta_0}{\parallel\beta\parallel}\\
	& = \frac{f(x)}{\parallel f'(x)\parallel}
	\end{align*}
\end{itemize}
\subsection{算法}
\subsubsection{Rosenblatt's 认知算法}
Rosenblatt's 认知算法是通过最小化误分类点到决策边界的距离的算法找到一个分隔超平面。在数学上，如果$ x_i^T\beta+\beta_0<0 $，但$ y_i=1 $，则表明误分类，类似地，如果$ x_i^T\beta+\beta_0>0 $，但$ y_i=-1 $也是误分类。那么就可以最小化如下目标函数，
\[ Min\quad D(\beta,\beta_0)=-\sum_{i\in\mathcal{M}}y_i(x_i^T\beta+\beta_0) \]
其中$ \mathcal{M} $是误分类的点集。该问题的求解和算法并不高效，见p131。
\subsubsection{一种更好的算法}
一种更好的算法可以如下定义，
\begin{align}
 \mathop{Max} \limits_{\beta,\beta_0,\parallel\beta\parallel=1}&\quad M\nonumber \\
 s.t. \quad y_i(x_i^T\beta+& \beta_0)\ge M\quad for \quad i=1,\cdots,N \label{op1}
\end{align}

可以看出约束条件（包括$ \parallel\beta\parallel=1 $）保证了所有的点离由$ \beta_0,\beta $决定的分隔面至少有符号距离$ M $，目标函数就是要找一个最大的$ M $。实际上，$ \parallel\beta\parallel=1 $不是必然要等于1的，从约束条件看，本质上应该是这样的，
\[ y_i(x_i^T\beta+\beta_0)\ge M\parallel\beta\parallel \]
那么也可以通过设置$ \parallel\beta\parallel=1/M $来修改前述优化设置，
\begin{align*}
\mathop{Min} \limits_{\beta,\beta_0}&\quad \frac{1}{2}\parallel\beta\parallel^2\\
s.t. \quad y_i(x_i^T\beta+& \beta_0)\ge 1\quad for \quad i=1,\cdots,N 
\end{align*}
目标函数之所以要设平方以及乘以$ \frac{1}{2} $完全是为了后面优化上的形式好看。那么上述目标函数的拉格朗日函数为，
\[ L_P=\frac{1}{2}\parallel\beta\parallel^2-\sum_{i=1}^{N}\alpha_i[y_i(x_i^T\beta+\beta_0)-1] \]
一阶导数为0就意味着，
\begin{align*}
\beta=&\sum_{i=1}^{N}\alpha_iy_ix_i\\
0=&\sum_{i=1}^{N}\alpha_iy_i
\end{align*}

当然，因为是不等式约束，必然也要满足库恩塔克定理，
\begin{equation*}
 \alpha_i[y_i(x_i^T\beta+\beta_0)-1]=0\quad\forall i 
\end{equation*}
\subsection{支持向量分类器}
优化问题\eqref{op1}固然不错，但是有个时候完全正确的分类会使分类器比较敏感(即方差大)，因此我们可能希望存在一定的误分类，但是分隔面是稳定的，具体而言，可以稍微修改式\eqref{op1}为,
\[y_i(x_i^T\beta+\beta_0)\ge M-\xi_i \quad \text{或者} \quad y_i(x_i^T\beta+\beta_0)\ge M(1-\xi_i)\]

其中，$ \forall i,\xi_i\ge 0,\sum_{i=1}^{N}\xi_i\le constant $。第一种方式直观，但在优化计算上存在困难。第二方式把$ \xi_i $看作是测试点处于错误一侧的距离占总间隔M的比例，虽然概念上稍显复杂，但计算上极大方便，一般采取该类表达。类似地，可以采用最小化范数的形式重新书写目标函数，
\begin{align*}
\mathop{Min} \limits_{\beta,\beta_0}&\quad \frac{1}{2}\parallel\beta\parallel^2\\
s.t. \quad y_i(x_i^T\beta+& \beta_0)\ge 1-\xi_i\\
\xi_i\ge 0,&\sum \xi_i\ge constant \quad \forall i
\end{align*}
实际上可以把$ \sum_{i=1}^{N}\xi_i\le constant $写入目标函数，这样就是，
\begin{align*}
\mathop{Min} \limits_{\beta,\beta_0}&\quad \frac{1}{2}\parallel\beta\parallel^2+C\sum_{i=1}^{N}\xi_i\\
s.t. \quad y_i(x_i^T\beta+& \beta_0)\ge 1-\xi_i,\xi_i\ge 0\quad \forall i\\
\end{align*}
其拉格朗日函数为，
\[ L_P=\frac{1}{2}\parallel\beta\parallel^2+C\sum_{i=1}^N\xi_i-\sum_{i=1}^{N}\alpha_i[y_i(x_i^T\beta+\beta_0)-(1-\xi_i)]-\sum_{i=1}^N\mu_i\xi_i \]
一阶条件以及库恩塔克约束如下，
\begin{align*}
\beta=\sum_{i=1}^{N}\alpha_iy_ix_i\\
0=\sum_{i=1}^{N}\alpha_iy_i\\
\alpha_i=C-\mu_i,\forall i\\
\alpha_i[y_i(x_i^T\beta+\beta_0)-(1-\xi_i)]=0\\
\mu_i\xi_i=0\\
y_i(x_i^T\beta+\beta_0)-(1-\xi_i)\ge 0
\end{align*}

一旦找到解$ \hat \beta,\hat \beta_0 $，就可以得到决策函数，
\[ \hat G(x)=sign[\hat f(x)]=sign[x^T\hat \beta+\hat \beta_0] \]
\subsection{支持向量机}
决策函数使用的是原始特征$ x $，实际上，我们也可以使其更具弹性。譬如使用$ x $的多项式或者样条形式，这样决策函数就为，
\[ \hat G(x)=sign[\hat f(x)]=sign[和h(x)^T\hat \beta+\hat \beta_0] \]

实际上，更具体点，对于一个新的观测$ x $，其决定函数$ f(x) $，
\begin{align*}
f(x)&=h(x)^T\beta+\beta_0\\
& = \sum_{i=1}^N\alpha_iy_i\langle h(x),h(x_i)\rangle+\beta_0
\end{align*}

可以看到上式仅仅涉及到$ h(x) $的内积，更进一步，我们根本不需要$ h(x) $的具体形式，我们只要求一个满足对称正定或半正定的核函数$ K(x,x') $\footnote{注意，$ x' $不是表示转置，表示训练观测，$ x $是一个新的观测。}，
\[ K(x,x')=\langle h(x),h(x')\rangle \]

在SVM中比较常用的核函数包括：
\begin{itemize}
	\item $ d $阶多项式核：$ K(x,x')=(1+\langle x,x'\rangle)^d $
	\item 径向核：$ K(x,x')=exp(-\gamma \parallel x-x'\parallel^2) $
	\item 神经网络核：$ K(x,x')=tanh( \kappa_1\langle x,x'\rangle+\kappa_2 ) $
\end{itemize}

\subsection{与Logist回归的关系}

